Turnbull China Bikeride/Turnbull China Bikeride - Disc 2.iso/BARNET/COMPILER/SATHER/!Sather/Library/Graphs/sa/digrph_vws

Text File | 1996-07-13 | 12KB | 340 lines

---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <[e-mail]>
-- Copyright (C) 1995, International Computer Science Institute
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
-------------------------------------------------------------------
-- Design Note:
--  It might be useful to have versions of these views which are
--  pre-parametrized over $RO_DIGRAPH or $DIGRAPH for convenience
--  These have been written and could be added, but it is not
--  clear whether they help just confuse matters
-------------------------------------------------------------------
class DIGRAPH_NODE_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{NTP} is
   -- A view of the nodes of a digraph as a set. This is useful for
   -- looking at set properties of the nodes in the graph, for instance,
   -- finding the union or intersection of the nodes in two graphs
   -- Please see the notes in the module file

   include RO_SET_INCL{NTP};

   private attr graph: GTP;

   create(g: GTP): SAME is   res::=new; res.graph:=g; return res; end;
   -- Create a new view of the nodes of "g"

   copy: SAME is
      -- Return a copy of the nodes in this set
      return #SAME(graph);
   end;

   has(n: NTP): BOOL is return graph.has_node(n) end;
   -- Return true if the original graph has the node "n"

   size: INT is return graph.n_nodes end;
   -- Return the number of nodes in the orignal graph

   elt!: NTP is loop yield graph.node! end; end;
   -- Return the nodes of the original graph

end;
-------------------------------------------------------------------
class DIGRAPH_EDGE_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{DIEDGE{NTP}} is
   -- View of the edges of a graph as a read-only set.
   -- Design Note:
   -- Letting this set be writable is interesting, but can lead to
   -- very confusing results due to aliasing.
   include RO_SET_INCL{DIEDGE{NTP}};

   private attr graph: GTP;
   -- Holds a pointer to the actual graph being viewed

   create(g: GTP): SAME is   res::=new;res.graph:=g;return res; end;
   -- Create a view of the set of edges of the digraph "g"

   has(e: DIEDGE{NTP}): BOOL is return graph.has_edge(e) end;
   -- Return true if the digraph contains the edge "e"

   size: INT is return graph.n_edges end;
   -- Returns the number of edges in the digraph

   elt!: DIEDGE{NTP} is loop yield graph.edge! end; end;
   -- Yields the edges of the digraph

   copy: SAME is return #(graph) end;
   -- Returns a copy of the original digraph

end;
-------------------------------------------------------------------
class DIGRAPH_INC_SET_VIEW{NTP,GTP<$DIGRAPH{NTP}} < $RO_SET{NTP} is
   -- View of the incoming edges into the node of a digraph.

   include RO_SET_INCL{NTP} has->, elt!->;

   private attr graph: GTP;
   -- A pointer to the original graph being viewed
   private attr dest: NTP;
   -- The node whose incoming edges are being viewed

   create(g: GTP,dest: NTP): SAME is
      -- Create a view of the set of incoming nodes to "dest" in the
      -- graph "g"
      res ::= new; res.graph := g; res.dest := dest;   return  res;
   end;

   has(n: NTP): BOOL is return graph.has_edge(#DIEDGE{NTP}(n,dest)) end;
   -- Return true if node "dest" has an incoming edge from "n"

   size: INT is return graph.n_incoming(dest) end;
   -- Return the number of incoming edges into "dest"

   elt!: NTP is loop yield graph.incoming!(dest) end; end;
   -- Yield the nodes which have edges to "dest"

   copy: SAME is return #(graph,dest) end;
   -- Return a copy of self

end;
-------------------------------------------------------------------
class DIGRAPH_OUTG_SET_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_SET{NTP} is
   -- View of the outgoing edges into the node of a digraph.
   include RO_SET_INCL{NTP};

   private attr graph: GTP;
   -- The graph being viewed
   private attr src: NTP;
   -- The node whose outgoing edges are being viewed

   create(g:GTP, src: NTP): SAME is return new.init(g,src);  end;

   private init(g: GTP,s: NTP): SAME is
      graph := g; src:=s; return self
   end;

   has(n: NTP): BOOL is return graph.has_edge(#DIEDGE{NTP}(src,n)) end;

   size: INT is return graph.n_outgoing(src) end;

   elt!: NTP is loop yield graph.outgoing!(src) end; end;

   copy: SAME is return #(graph,src) end;
   -- Return a copy of self

end;
-------------------------------------------------------------------
class DIGRAPH_REV_DIGRAPH_VIEW{NTP,GTP<$DIGRAPH{NTP}} < $DIGRAPH{NTP} is
   -- A view of a digraph with all edges reversed.  Unlike most other
   -- views, this view of the graph permits modification operations,
   -- which are translated into operations on the original graph.
   -- Care should be taken in operations that involved both the
   -- original graph and this view

   include DIGRAPH_INCL{NTP};

   private attr source:GTP;

   create(m:GTP): SAME is
      -- Create a subgraph of "m"
      res ::= new;
      res.source := m;
      return(res);
   end;

   add_node: NTP is return source.add_node end;

   add_node(n: NTP): NTP is   return source.add_node(n);  end;

   connect(e: DIEDGE{NTP}) is  source.connect(e.reverse);  end;

   delete_node(n: NTP) is source.delete_node(n) end;

   disconnect(e: DIEDGE{NTP}) is source.disconnect(e.reverse) end;

   has_node(n: NTP): BOOL is return source.has_node(n) end;

   has_edge(e: DIEDGE{NTP}): BOOL is return source.has_edge(e.reverse) end;

   n_edges: INT is
      i ::= 0;  loop n ::= node!; i := i +  n_incoming(n); end;
      return i;
   end;

   n_nodes: INT is return(source.n_nodes) end;

   n_incoming(n: NTP): INT is return source.n_outgoing(n) end;

   n_outgoing(n: NTP): INT is return source.n_incoming(n) end;

   node!: NTP is loop yield source.node! end; end;

   edge!: DIEDGE{NTP} is
      loop n ::= node!;
     loop inc::= incoming!(n); yield #DIEDGE{NTP}(inc,n); end;
      end;
   end;

   incoming!(once n: NTP): NTP is loop yield source.outgoing!(n) end; end;

   outgoing!(once n: NTP): NTP is loop yield source.incoming!(n) end; end;

end;
-------------------------------------------------------------------
class FILTERGRAPH_DIGRAPH_VIEW{NTP,GTP<$RO_DIGRAPH{NTP}} < $RO_DIGRAPH{NTP} is
   -- View a graph through a node/edge filter predicate
   -- Only the nodes and edges that satisfy the predicates are visible
   -- as nodes and edges in this view.
   -- If the node predicate is "np" and the edge predicate is "ep",
   -- Nodes which satisfy "np" are in the graph
   -- Edges which satisfy "ep" and whose nodes are both satisfied by
   -- "np" are in the graph.


   include RO_DIGRAPH_INCL{NTP};

   private attr source:GTP;
   private attr np: ROUT{NTP}: BOOL;
   private attr ep: ROUT{DIEDGE{NTP}}: BOOL;

   create(m:GTP,np:ROUT{NTP}:BOOL,ep:ROUT{DIEDGE{NTP}}:BOOL): SAME
   -- Create a subgraph of "m". It consists of nodes that pass the
   -- node filter "np"  and edges that pass the edge filter,
   -- whose ends pass the node filter.
   -- Nodes n that belong to "m" and np.call(n) = true
   -- Edges e (1) m.has_edge(e)
   --         (2) np.call(e.first) and np.call(e.second)
   --         (3) ep.call(e)
   is
      res ::= new;
      res.source := m;
      res.np := np;
      res.ep := ep;
      return(res);
   end;

   create(m:GTP,np:ROUT{NTP}:BOOL): SAME is
      -- Create a subgraph of "m", which includes all nodes that pass
      -- the node filter "np"
      res ::= new;
      res.source := m;
      res.np := np;
      res.ep := void;
      return(res);
   end;

   has_node(n: NTP): BOOL is return source.has_node(n) and np.call(n)  end;

   has_edge(e: DIEDGE{NTP}): BOOL is
      -- An edge exists here if and only if it exists in the source,
      -- both its end points pass the node filter and the edge itself
      -- passes the edge filter
      ef ::= e.first; es ::= e.second;
      if void(ep) then
     return source.has_edge(e) and np.call(ef) and np.call(es);
      else
     return source.has_edge(e) and np.call(ef) and np.call(es) and
           ep.call(e)
      end;
   end;

   n_nodes: INT is
      i ::= 0; loop n ::= node!; i := i + 1; end;   return i;
   end;

   n_edges: INT is
      i ::= 0;  loop n ::= node!; i := i +  n_incoming(n); end;
      return i;
   end;

   n_incoming(n: NTP): INT is
      -- Compute the number of edges by actually iterating over the
      -- edges and returning the resulting number found
      i ::= 0; loop discard ::= incoming!(n); i := i + 1; end;
      return i;
   end;

   n_outgoing(n: NTP): INT is
      -- Compute the number of outgoing edges by actually iterating over them
      i ::= 0; loop discard ::= outgoing!(n); i := i + 1; end;
      return i;
   end;

   node!: NTP is
      -- Yield all the nodes in the source that pass the filter node predicate
      loop n ::= source.node!;  if np.call(n) then yield n end;  end;
   end;

   edge!: DIEDGE{NTP} is
      loop n ::= node!;
     loop inc::= incoming!(n); yield #DIEDGE{NTP}(inc,n); end;
      end;
   end;

   incoming!(once n: NTP): NTP
      pre has_node(n)
      post has_edge(#DIEDGE{NTP}(n,result))
   -- Yield all the incoming nodes from node "n". Yield only nodes
   -- which pass the filter and are connected by an edge that passes the filter
   is
      loop inc ::= source.incoming!(n);
     if np.call(inc) and ep.call(#DIEDGE{NTP}(inc,n)) then yield inc end;
      end;
   end;

   outgoing!(once n: NTP): NTP
   -- Yield all the outgoing nodes from node "n". Yield only nodes
   -- which pass the filter and are connected by an edge that passes the filter
      pre has_node(n)
      post has_edge(#DIEDGE{NTP}(n,result))
   is
      loop og ::= source.outgoing!(n);
     if np.call(og) and ep.call(#DIEDGE{NTP}(n,og)) then yield og end;
      end;
   end;

end;
-------------------------------------------------------------------
-- Note:
-- Simplifications of corresponding class with the graph argument
-- where the graph is assumed to be a generic $RO_DIGRAPH
-- This version is convenient to use but may be considerably less
-- efficient than the version with 2 parameters.
-- If the type of the graph is known, the parametrized version
-- has a strongly typed pointer to the actual graph, allowing
-- many optimizations such as inlining, in addition to avoiding
-- dispatching
-------------------------------------------------------------------
class DIGRAPH_NODE_SET_VIEW{NTP} < $RO_SET{NTP} is
   -- Simplification of DIGRAPH_NODE_SET_VIEW which has a pointer
   -- to a generic $DIGRAPH{NTP}. Less efficient
   include DIGRAPH_NODE_SET_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
-------------------------------------------------------------------
class DIGRAPH_EDGE_SET_VIEW{NTP} < $RO_SET{DIEDGE{NTP}} is
   -- Simplification of DIGRAPH_EDGE_SET_VIEW with 2 parameters
   include DIGRAPH_EDGE_SET_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
-------------------------------------------------------------------
class DIGRAPH_INC_SET_VIEW{NTP} < $RO_SET{NTP} is
   -- Simplification of DIGRAPH_INC_SET_VIEW with 2 parameters
   include DIGRAPH_INC_SET_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
-------------------------------------------------------------------
class DIGRAPH_OUTG_SET_VIEW{NTP} < $RO_SET{NTP} is
   -- Simplification of DIGRAPH_OUTG_SET_VIEW with 2 parameters
   include DIGRAPH_OUTG_SET_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
-------------------------------------------------------------------
class FILTERGRAPH_DIGRAPH_VIEW{NTP} < $RO_DIGRAPH{NTP} is
   -- Simplification of FILTERGRAPH_DIGRAPH_VIEW
   include FILTERGRAPH_DIGRAPH_VIEW{NTP,$RO_DIGRAPH{NTP}};
end;
-------------------------------------------------------------------
class DIGRAPH_REV_DIGRAPH_VIEW{NTP} < $DIGRAPH{NTP} is
   -- Simplification of DIGRAPH_REV_DIGRAPH_VIEW
   include DIGRAPH_REV_DIGRAPH_VIEW{NTP,$DIGRAPH{NTP}};
end;
-------------------------------------------------------------------